package 中等.分组循环;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。
 * 在一次操作中，你可以选择任意两个下标 i 和 j，如果 满足 |nums[i] - nums[j]| <= limit ，则交换 nums[i] 和 nums[j] 。
 * 返回执行任意次操作后能得到的 字典序最小的数组 。
 * 如果在数组 a 和数组 b 第一个不同的位置上，数组 a 中的对应元素比数组 b 中的对应元素的字典序更小，则认
 * 为数组 a 就比数组 b 字典序更小。例如，数组 [2,10,3] 比数组 [10,2,3] 字典序更小，下标 0 处是两个数组第一个不同的位置，且 2 < 10 。
 *
 * @ https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/description/
 * @date 2024/11/11
 */
public class 交换得到字典序最小的数组_2948 {

    public static void main(String[] args) {

    }

    /**
     * 分组循环
     * 排序后，相邻的两个数差 <= limit 的段，都是可以通过操作得到排序的结果
     * 然后根据下标进行排序填充
     */
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int[][] arr = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = new int[]{nums[i], i};
        }
        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        int left = 0;
        while (left < arr.length) {
            List<Integer> idxList = new ArrayList<>();
            idxList.add(arr[left][1]);
            int right = left + 1;
            while (right < arr.length && arr[right][0] - arr[right - 1][0] <= limit) {
                idxList.add(arr[right][1]);
                right++;
            }
            idxList.sort((a, b) -> a - b);
            for (int i = left, j = 0; i < right; i++, j++) {
                nums[idxList.get(j)] = arr[i][0];
            }
            left = right;
        }

        return nums;
    }

}
